class Solution
{
public:
    int shortestPathBinaryMatrix(vector<vector<int>> &grid)
    {
        if (grid[0][0] == 1)
        {
            return -1;
        }
        grid[0][0] = 1;

        int n = grid.size();

        queue<pair<int, int>> q;
        q.push({0, 0});

        int step = 0;

        while (!q.empty())
        {
            ++step;
            int qSize = q.size();
            for (int _ = 0; _ < qSize; _++)
            {
                auto [row, col] = q.front();
                q.pop();

                if (row == n - 1 && col == n - 1)
                {
                    return step;
                }

                if (row < n - 1 && grid[row + 1][col] == 0)
                {
                    q.push({row + 1, col});
                    grid[row + 1][col] = 1;
                }

                if (col < n - 1 && grid[row][col + 1] == 0)
                {
                    q.push({row, col + 1});
                    grid[row][col + 1] = 1;
                }

                if (row > 0 && grid[row - 1][col] == 0)
                {
                    q.push({row - 1, col});
                    grid[row - 1][col] = 1;
                }

                if (col > 0 && grid[row][col - 1] == 0)
                {
                    q.push({row, col - 1});
                    grid[row][col - 1] = 1;
                }

                if (row < n - 1 && col < n - 1 && grid[row + 1][col + 1] == 0)
                {
                    q.push({row + 1, col + 1});
                    grid[row + 1][col + 1] = 1;
                }

                if (row < n - 1 && col > 0 && grid[row + 1][col - 1] == 0)
                {
                    q.push({row + 1, col - 1});
                    grid[row + 1][col - 1] = 1;
                }

                if (row > 0 && col < n - 1 && grid[row - 1][col + 1] == 0)
                {
                    q.push({row - 1, col + 1});
                    grid[row - 1][col + 1] = 1;
                }

                if (row > 0 && col > 0 && grid[row - 1][col - 1] == 0)
                {
                    q.push({row - 1, col - 1});
                    grid[row - 1][col - 1] = 1;
                }
            }
        }

        return -1;
    }
};